package com.example.hot100;

import com.example.tree.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 *  展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 *  展开后的单链表应该与二叉树 先序遍历 顺序相同。
 *
 *  示例 1：
 * 输入：root = [1,2,5,3,4,null,6]
 * 输出：[1,null,2,null,3,null,4,null,5,null,6]
 *
 *  示例 2：
 * 输入：root = []
 * 输出：[]
 *
 *  示例 3：
 * 输入：root = [0]
 * 输出：[0]
 */
public class Leetcode114_Flatten {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);
        new Solution().flatten(root);

        TreeNode tmp = root;
        while (tmp != null) {
            System.out.println(tmp.val);
            tmp = tmp.right;
        }
    }

    static class Solution {
        /**
         * 后序遍历，并同时修改指针(递归实现)
         * 右子树->左子树->根节点
         * 因为后序遍历不会丢失节点的子节点信息
         * @param root
         */
        public void flatten2(TreeNode root) {
            afterOrder(root);
        }

        private TreeNode pre;
        private void afterOrder(TreeNode root) {
            if (root == null) return;
            afterOrder(root.right);
            afterOrder(root.left);

            root.right = pre;
            root.left = null;
            pre = root;

        }

        /**
         * 方法一:前序遍历和展开同步进行(迭代)
         * @param root
         */
        public void flatten1(TreeNode root) {
            if (root == null) {
                return;
            }
            Deque<TreeNode> stack = new LinkedList<>();
            stack.push(root);
            TreeNode pre = null;

            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();

                if (pre != null) {
                    pre.left = null;
                    pre.right = cur;
                }

                if (cur.right != null) stack.push(cur.right); // 先将右节点入栈

                if (cur.left != null) stack.push(cur.left); // 再入栈左节点

                pre = cur;
            }
        }

        public void flatten(TreeNode root) {
            flatten2(root);
        }
    }
}
